/*
 * Copyright (c) 2012, Inc.
 * Permission to use, copy, modify, distribute and sell this software
 * and its documentation for any purpose is hereby granted without fee,
 * provided that the above copyright notice appear in all copies and
 * that both that copyright notice and this permission notice appear
 * in supporting documentation.  Silicon Graphics makes no
 * representations about the suitability of this software for any
 * purpose.  It is provided "as is" without express or implied warranty.
 */

//=============================================================================
/**
 *  @file    stl_algobase_ex.h
 *
 *  This is an internal header file, included by other library headers.
 *
 *  $Id: stl_algobase_ex.h 2012-10-04 04:28:24Z shawn chen$
 *
 *  @author chen xiaowei<cxwshawn@yeah.net>.
 */
//=============================================================================

#ifndef STL_ALGOBASEEX_H_INCLUDED
#define STL_ALGOBASEEX_H_INCLUDED

namespace stdex
{

#   if defined __linux

#include <bits/stl_iterator_base_types.h>
#include <bits/cpp_type_traits.h>

template<bool, typename>
    struct __copy_ex
    {
      template<typename _II, typename _OI, typename Pred>
        static _OI
        copy(_II __first, _II __last, _OI __result, Pred pred)
        {
            //todo:
          for (; __first != __last; ++__first)
          {
              if( pred(*__first) )
              {
                *__result = *__first;
                ++__result;
              }
          }
          return __result;
        }
    };
/*
  template<bool _BoolType>
    struct  __copy_ex<_BoolType, std::random_access_iterator_tag>
    {
      template<typename _II, typename _OI, typename Pred>
        static _OI
        copy(_II __first, _II __last, _OI __result, Pred pred)
        {
	  typedef typename std::iterator_traits<_II>::difference_type _Distance;
	  for(_Distance __n = __last - __first; __n > 0; --__n)
	    {
            if( pred(*__first) )
            {
                *__result = *__first;
                ++__result;
            }
	      ++__first;
	    }
	  return __result;
	}
    };


  template<>
    struct  __copy_ex<true, std::random_access_iterator_tag>
    {
      template<typename _Tp, typename Pred>
        static _Tp*
        copy(const _Tp* __first, const _Tp* __last, _Tp* __result, Pred pred)
        {

            while( __first != __last )
            {
                if( pred(*__first) )
                {
                    *__result = *__first;
                    ++__result;
                }
                ++__first;
            }
            return __result;
        }
    };
    template<>
    struct  __copy_ex<false, std::random_access_iterator_tag>
    {
      template<typename _Tp, typename Pred>
        static _Tp*
        copy(const _Tp* __first, const _Tp* __last, _Tp* __result, Pred pred)
        {
          while( __first != __last )
            {
                if( pred(*__first) )
                {
                    *__result = *__first;
                    ++__result;
                }
                ++__first;
            }
            return __result;
        }
    };
*/
template<typename _II, typename _OI, typename UnaryPredicate>
    inline _OI
    __copy_aux_ex(_II __first, _II __last, _OI __result, UnaryPredicate pred)
    {
      typedef typename std::iterator_traits<_II>::value_type _ValueTypeI;
      typedef typename std::iterator_traits<_OI>::value_type _ValueTypeO;
      typedef typename std::iterator_traits<_II>::iterator_category _Category;
      const bool __simple = (std::__is_scalar<_ValueTypeI>::__value
	                     && std::__is_pointer<_II>::__value
	                     && std::__is_pointer<_OI>::__value
			     && std::__are_same<_ValueTypeI, _ValueTypeO>::__value);
        //todo: whether need to judge if the pred is unary predicate.
      return stdex::__copy_ex<__simple, _Category>::copy(__first, __last, __result, pred);
    }

template<bool, bool>
    struct __copy_normal
    {
      template<typename _II, typename _OI, typename Pred>
        static _OI
        copy_n(_II __first, _II __last, _OI __result, Pred pred)
        { return stdex::__copy_aux_ex(__first, __last, __result, pred); }
    };

  template<>
    struct __copy_normal<true, false>
    {
      template<typename _II, typename _OI, typename Pred>
        static _OI
        copy_n(_II __first, _II __last, _OI __result, Pred pred)
        { return stdex::__copy_aux_ex(__first.base(), __last.base(), __result, pred); }
    };

  template<>
    struct __copy_normal<false, true>
    {
      template<typename _II, typename _OI, typename Pred>
        static _OI
        copy_n(_II __first, _II __last, _OI __result, Pred pred)
        { return _OI(stdex::__copy_aux_ex(__first, __last, __result.base(), pred)); }
    };

  template<>
    struct __copy_normal<true, true>
    {
      template<typename _II, typename _OI, typename Pred>
        static _OI
        copy_n(_II __first, _II __last, _OI __result, Pred pred)
        { return _OI(stdex::__copy_aux_ex(__first.base(), __last.base(),
				     __result.base(), pred)); }
    };

#   undef copy_if

/**
   *  @brief Copies the range [first,last) into result if the input elements
   *  is consistent with the pred condition.
   *  @param  first  An input iterator.
   *  @param  last   An input iterator.
   *  @param  result An output iterator.
   *  @param  pred   An unary functor.
   *  @return
  */

  template< class InputIterator, class OutputIterator, class UnaryPredicate >
  inline OutputIterator copy_if( InputIterator __first, InputIterator __last,
                        OutputIterator __result,
                        UnaryPredicate pred )
    {
      // concept requirements
      __glibcxx_function_requires(_InputIteratorConcept<InputIterator>)
      __glibcxx_function_requires(_OutputIteratorConcept<OutputIterator,
	    typename iterator_traits<InputIterator>::value_type>)
      __glibcxx_requires_valid_range(__first, __last);

       const bool __in = std::__is_normal_iterator<InputIterator>::__value;
       const bool __out = std::__is_normal_iterator<OutputIterator>::__value;
       return stdex::__copy_normal<__in, __out>::copy_n(__first, __last,
						      __result, pred);
    }

#   elif defined WIN32 || defined _WIN64 || defined WIN64 || defined _WIN32_WINNT

#   undef copy_if

template<class InputIterator, class OutputIterator, class UnaryPredicate>
OutputIterator copy_if(InputIterator first, InputIterator last,
                    OutputIterator d_first, UnaryPredicate pred)
{
    while ( first != last ) {
        if( pred(*first) )
            *d_first++ = *first;
         first++;
    }
    return d_first;
}

#   else
template<class InputIterator, class OutputIterator, class UnaryPredicate>
OutputIterator copy_if(InputIterator first, InputIterator last,
                    OutputIterator d_first, UnaryPredicate pred)
{
    while ( first != last ) {
        if( pred(*first) )
            *d_first++ = *first;
         first++;
    }
    return d_first;
}

#   endif

/**
 * the following function parameters must be consistent with the standard iterator.
 */

#undef copy_n

template< class InputIterator, class Size, class OutputIterator>
OutputIterator copy_n(InputIterator first, Size count, OutputIterator result)
{
    if ( count > 0 ) {
        *result++ = *first;
        for ( Size i = 1; i < count; ++i) {
            *result++ = *++first;
        }
    }
    return result;
}

#   undef copy_backward_if

template< class BidirectionalIterator1, class BidirectionalIterator2 , class UnaryPredicate>
BidirectionalIterator2 copy_backward_if(BidirectionalIterator1 first,
                                     BidirectionalIterator1 last,
                                     BidirectionalIterator2 d_last, UnaryPredicate pred)
{
    while (first != last) {
        if( pred(*--last) )
        {
            *(--d_last) = *last;
        }
    }
    return d_last;
}

#   undef itoa

template<class ForwardIterator, class T>
void iota(ForwardIterator first, ForwardIterator last, T value)
{
    while(first != last) {
        *first++ = value;
        ++value;
    }
}

}

#endif // STL_ALGOBASEEX_H_INCLUDED
